686. Утверждение Гольдбаха - 2

Утверждение Гольдбаха. Для любого натурального четного n ³ 4 существует как минимум одна пара простых чисел (p₁, p₂), для которой n = p₁ + p₂.

В задаче требуется найти количество таких пар простых чисел для заданного n. Пары (p₁, p₂) и (p₂, p₁) считаются одинаковыми.

Вход. Каждая строка содержит четное натуральное n (4 £ n < 2¹⁵). Признак конца входных данных n = 0.

Выход. Для каждого входного n в отдельной строке вывести количество пар простых чисел (p₁, p₂), для которых n = p₁ + p₂.

Пример входа

6
10
12
0
 

Пример выхода

1
2
1
 

РЕШЕНИЕ

простые числа, решето Эратосфена

Анализ алгоритма

При помощи решета Эратосфена сгенерируем массив primes, для которого primes[i] = 1 для простых i и primes[i] = 0 иначе. Далее следует подсчитать количество таких пар (p₁, n - p₁), что p₁ и n - p₁ – простые числа, p₁ £ n - p₁.

Пример

Для n = 6 имеется одна пара (3, 3). Для n = 10 имеются две пары: (3, 7) и (5, 5).

Реализация алгоритма

При помощи решета Эратосфена сгенерируем массив primes для дальнейшего тестирования чисел на простоту. Поскольку n < 2¹⁵, то достаточно положить длину массива MAX равной 32768.

#define MAX 32768

int primes[MAX];

void gen_primes(void)

{

int i, j;

for(i = 0; i < MAX; i++) primes[i] = 1;

for(i = 2; i <= (int)sqrt(1.0*MAX);i++)

if (primes[i])

for(j = i; j * i < MAX; j++) primes[i*j] = 0;

}

Функция FindSol(n) вычисляет количество разных пар простых чисел (p₁, p₂), для которых n = p₁ + p₂. Для этого достаточно перебрать такие пары (p₁, p₂), для которых p₁ £ p₂. Откуда следует, что p₁ £ n/2. Или то же самое что подсчитать количество пар (i, n – i), для которых i и n – i простые, 2 £ i £ n/2.

int FindSol(int n)

{

int i, res = 0;

for(i = 2; i <= n / 2; i++)

if (primes[i] && primes[n-i]) res++;

return res;

}

Сначала генерируем массив primes при помощи функции gen_primes. После чего для каждого входного значения n выводим FindSol(n).

gen_primes();

while(scanf("%d",&n), n)

printf("%d\n",FindSol(n));